package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.Arrays;

/**
 * 描述：
 * 给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/array-of-doubled-pairs
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author 🧑 ‍wanwei
 * @since 2023-02-02 10:54
 */
public class CX954 {

    public static void main(String[] args) {
        int[] arr = {-6,-3};
        System.out.println(canReorderDoubled(arr));
    }

    /**
     * 奇数位永远是前一位的两倍
     * <p>
     * 1.排序
     * 2.计算每个数 除2后的值
     * 3.有则消除 如果所有的数都能消除 则返回true 否则返回false
     *
     * @param arr
     * @return
     */
    public static boolean canReorderDoubled(int[] arr) {
        //正负值得分开
        int[] arrPositive = new int[arr.length];
        int[] arrNegative = new int[arr.length];
        int[] arrNegativeReverse = new int[arr.length];

        int totalPositive = 0;
        int totalNegative = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= 0) {
                totalPositive++;
                arrPositive[i] = arr[i];
            } else {
                totalNegative++;
                arrNegative[i] = arr[i];
            }
        }
        if (totalPositive % 2 != 0 || totalNegative % 2 != 0) {
            return false;
        }
        Arrays.sort(arrPositive);
        Arrays.sort(arrNegative);
        for (int i = 0; i < arrNegative.length; i++) {
            arrNegativeReverse[arrNegativeReverse.length -i - 1] = arrNegative[i];
        }
        return canReorderDoubled2(arrPositive) && canReorderDoubled2(arrNegativeReverse);
    }

    public static boolean canReorderDoubled2(int[] arr) {
        //整除2后的值
        int[] arrNew = new int[arr.length];

        //是否能被2整除
        boolean[] arrFlagNew = new boolean[arr.length];
        boolean[] used = new boolean[arr.length];

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 == 0) {
                arrNew[i] = arr[i] / 2;
                arrFlagNew[i] = true;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            boolean flag = false;
            if (used[i]) {
                continue;
            }
            for (int j = i + 1; j < arrNew.length; j++) {
                if (used[j]) {
                    continue;
                }
                if (arrFlagNew[j] && arr[i] == arrNew[j]) {
                    flag = true;
                    used[i] = true;
                    used[j] = true;
                    break;
                }
            }
            if (!flag) {
                return false;
            }
        }

        return true;
    }
}
